原题链接:[UVA 1347] Tour

原题大意:一个图上有$n$个点,给定他们的坐标.现在分别有两个人在最左端和最右端的点上移动,各个点的$x$坐标都是不同的.两个人不能走到同一个点上,问走过的总距离最少是多少.
数据范围:
$1 \leq n \leq 1000$

思路

显然让两个人从左边走到右边,又从右边走到左边是非常蛋疼的.不过由于距离是欧式距离是双向的,不妨把这个问题变成两个人同时从起点出发,且经过的点不重复的最小距离.这就很像一个网络流的模型,但是费用流做不了,或者说很难做,首先必须保证所有的点都经过了,其次边可能达到$10^6$的级别,这是跑不了的.
现在来考虑DP,一个比较直接的想法就是$f[i][j]$表示第一个人走到了$i$,第二个人走到了$j$.入口出口都比较好想,但是没法转移:因为这个状态根本没有一个是否能走到下一个点的信息,假如现在要计算$f[i][j]$那$i+1$这个点是否被用过了,根本不知道,没法转移.
既然如此,就把状态修改成这样:$f[i][j]$表示$1~max(i,j)$这些点都被经过了的前提下,两者位置分别是$i,j$,剩余还要走的最小距离是多少.这个状态就可以解决掉之前的问题,即可以知道一个信息:$i+1$这个点有没有被用过.在此基础上,减少一定的讨论,可以规定$i>j$,这样就可以在不影响答案的前提下去减少一些讨论.不过这样还是不能转移,因为当前是$f[i][j]$的时候,如果直接走到$i+2$这个点,显然$i+1$这个点就走不了了,因为状态根本没法表示了,但是这个转移的时候又没有限制,这里有个很巧妙的想法:禁止这样的转移,每次转移就只能走到$i+1$.为什么这样是正确的呢,因为当走到$i+2$的时候,其实第二个人必须要走过$i+1$这个点,不妨就让第二个人先转移到$i+1$再让第一个人走到$i+2$上,这个结果上是符合要求的,也不会出现一个点没有被用到的情况.
重新梳理一下过程:
状态:$f[i][j]$表示当前已经走过了$1-i$这些点,并且$i>j$.两者分别在$i,j$这两点上时,剩余还要走的距离的所有集合里最小的具体值是多少.
入口:$f[n][n - 1] = dist(n,n-1)$
转移:转移有两种,一种是从$i$走到$i+1$.这种情况下就是$f[i + 1][j] + dist(i,i+1)$.另一种是第二个人走到$i+1$,即$f[i + 1][i] + dist(i + 1,j)$注意这里本来是$f[i][i + 1]$的,但是之前定义的时候要求保证$i>j$所以调换了顺序.
出口:答案就是$dist(1,2) + f[2][1]$

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1005;
int n;
double x[N],y[N],f[N][N];
double gdist(int a,int b)
{
	double dx = x[a] - x[b],dy = y[a] - y[b];
	return sqrt(dx * dx + dy * dy);
}
int main()
{
	while((scanf("%d",&n)) == 1)
	{
		for(int i = 1;i <= n;++i)	scanf("%lf%lf",&x[i],&y[i]);
		for(int i = 1;i <= n;++i)	for(int j = 1;j <= n;++j)	f[i][j] = 1e10;
		f[n][n - 1] = gdist(n,n - 1);		
		for(int i = n - 1;i >= 1;--i)
		{
			for(int j = i - 1;j >= 1;--j)
			{
				auto& v = f[i][j];
				v = min(v,f[i + 1][j] + gdist(i,i + 1));
				v = min(v,f[i + 1][i] + gdist(j,i + 1));
			}
		}
		// cout << f[2][1] << endl;
		printf("%.2lf\n",f[2][1] + gdist(1,2));
	}	
    return 0;
}